package com.moyoutian.sort;

import com.moyoutian.utils.ArrayUtils;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 快速排序练习
 * 思想概述：
 * 随便找一个数字作为基准，使其将数组分割。 大的在一边，小的在一边
 * 然后在左右开弓套娃，直至最后剩余 1个元素
 */
public class QuickSort {

    public static void main(String[] args) {
//        int[] ints = ArrayUtils.getIntAr(10, 5);
//        int[] ints = new int[]{1, 0, 3, 2, 2, 1, 3, 3, 1, 4};
//        ArrayUtils.printArray("初始", ints);
//        sort(ints);
//        ArrayUtils.printArray("排序后", ints);
        test();
    }

    /**
     * 测试程序
     */
    public static void test() {
        // 测试次数
        int testCount = 50000;
        for (int i = 0; i < testCount; i++) {
            test(ArrayUtils.getIntAr());
        }
    }

    public static void test(int[] ints) {
        int[] copy_ints_sort = Arrays.stream(ints).sorted().toArray();
        sort(ints);
        if (!Arrays.equals(copy_ints_sort, ints)) {
            System.out.println("QuickSort.test ");
        }
    }

    public static void sort(int[] ints) {
        sort(ints, 0, ints.length - 1);
    }

    public static void sort(int[] ints, int l, int r) {
        if (l < r) {
            int s = sortBothSides(ints, l, r);
            if (s - 1 > l) {
                sort(ints, l, s - 1);
            }
            if (s + 1 < r) {
                sort(ints, s + 1, r);
            }
        }
    }

    /**
     * 将一个数组按基准坐标值，分成两份
     *
     * @param ints 数组
     * @param l    左边界
     * @param r    又边界
     */
    public static int sortBothSides(int[] ints, int l, int r) {
        int tmp_r = r;
        int tmp = ints[tmp_r];
        while (l < r) {
            while (ints[l] < tmp && l < r) {
                l++;
            }
            while (ints[r] >= tmp && r > l) {
                r--;
            }
            if (l < r) {
                ArrayUtils.swap(ints, l, r);
            }
        }

        ArrayUtils.swap(ints, r, tmp_r);
        return r;
    }

}
